{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "f5347a34fd50441f5f5472f6b3c4b278",
     "grade": false,
     "grade_id": "cell-230630b07a6bced0",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "# Exercise 3: Dynamic Programming\n",
    "\n",
    "## 1) Policy Evaluation\n",
    "\n",
    "After your master thesis you decide to study on and do you beer-bachelor.\n",
    "Therefore, you have to drink three beers in three different pubs. \n",
    "There are six pubs available in town, you start at home and will (hopefully) end up at home. The problem is depicted in the following picture:\n",
    "\n",
    "![](Beer-Bachelor.png)\n",
    "\n",
    "In our first example we follow the 50/50 policy. \n",
    "So after drinking in a pub - e.g. Auld Triangle, there is a $50 \\, \\%$ probability to go \"up\" to the Globetrotter and  $50\\, \\%$ probability to go \"down\" to the Black Sheep.\n",
    "Evaluate the state values using policy evaluation ($v_\\mathcal{X} = \\mathcal{R}_\\mathcal{X} + \\gamma \\mathcal{P}_{xx'} v_\\mathcal{X}$):\n",
    "\n",
    "\\begin{align*}\n",
    "\\begin{bmatrix}\n",
    "v^{50/50}_{1}\\\\\n",
    ".\\\\\n",
    ".\\\\\n",
    ".\\\\\n",
    "v^{50/50}_{n}\\\\\n",
    "\\end{bmatrix}\n",
    "=\n",
    "\\begin{bmatrix}\n",
    "\\mathcal{R}^{50/50}_{1}\\\\\n",
    ".\\\\\n",
    ".\\\\\n",
    ".\\\\\n",
    "\\mathcal{R}^{50/50}_{n}\\\\\n",
    "\\end{bmatrix}\n",
    "+\n",
    "\\gamma\n",
    "\\begin{bmatrix}\n",
    "{p}^{50/50}_{11}&...&{p}^{50/50}_{1n}\\\\\n",
    ".& &.\\\\\n",
    ".& &.\\\\\n",
    ".& &.\\\\\n",
    "{p}^{50/50}_{n1}&...&{p}^{50/50}_{nn}\\\\\n",
    "\\end{bmatrix}\n",
    "\\begin{bmatrix}\n",
    "v^{50/50}_{1}\\\\\n",
    ".\\\\\n",
    ".\\\\\n",
    ".\\\\\n",
    "v^{50/50}_{n}\\\\\n",
    "\\end{bmatrix}\n",
    "\\end{align*}\n",
    "\n",
    "The rewards are given as negative numbers next to the arrows and represent the distances between two bars as a penalty.\n",
    "In this exercise we will set $\\gamma = 0.9$. \n",
    "In the shown problem we have $n = 8$ states (pubs, including start-home and end-home), ordered as given by the state space:\n",
    "\n",
    "\\begin{align*}\n",
    "\\mathcal{X} =\n",
    "\\left\\lbrace \\begin{matrix}\n",
    "\\text{Start: Home}\\\\\n",
    "\\text{Auld Triangle}\\\\\n",
    "\\text{Lötlampe}\\\\\n",
    "\\text{Globetrotter}\\\\\n",
    "\\text{Black Sheep}\\\\\n",
    "\\text{Limericks}\\\\\n",
    "\\text{Fat Louis}\\\\\n",
    "\\text{End: Home}\\\\\n",
    "\\end{matrix}\n",
    "\\right\\rbrace\n",
    "\\end{align*}\n",
    "\n",
    "Use a little python script to calculate the state values!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "30a73670fc81c873cfd9b64ea3df545f",
     "grade": true,
     "grade_id": "cell-16d89aafe7b794c3",
     "locked": false,
     "points": 0,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "YOUR ANSWER HERE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "b37e13abd8538840a34976ee43b0ea15",
     "grade": false,
     "grade_id": "cell-c8311eb3e04caeaf",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "# define given parameters\n",
    "gamma = 0.9 # discount factor\n",
    "\n",
    "# YOUR CODE HERE\n",
    "raise NotImplementedError()\n",
    "\n",
    "print(v_X)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "224b94cd650e819917b244f69fdc1103",
     "grade": false,
     "grade_id": "cell-707636577622b626",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## 2) Exhaustive Policy Search \n",
    "\n",
    "From now on use $\\gamma = 1$.\n",
    "\n",
    "As you have pre knowledge from your master degree, you try to minimize the distance of the way you have to take during your tour in order to have more time in the pubs. Therefore, you perform the following exhaustive search algorithm:\n",
    "\n",
    "1. Write down all possible path-permutations and calculate the distances.\n",
    "2. Which is the best path concerning most beer per distance?\n",
    "3. Derive the formula to calculate the number of necessary path comparisons. \n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "6a8296c845ae57a09b886c3e42a1ffba",
     "grade": true,
     "grade_id": "cell-e069b4ff0546056a",
     "locked": false,
     "points": 0,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "YOUR ANSWER HERE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "d38c1b154628492911360f58bee39d56",
     "grade": false,
     "grade_id": "cell-c82401280b863042",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## 3) Dynamic Programming - The Idea\n",
    "\n",
    "Trying out all combinations might not be best for your liver, so you want to solve the problem above using dynamic programming. \n",
    "\n",
    "Making use of value iteration, derive the values resulting from the optimal policy: $v_{i+1}^*(x_k) = \\text{max}_u (r_{k+1} + v_{i}^*(x_{k+1}))$.\n",
    "\n",
    "Hint: There is only one policy improvement step needed.\n",
    "\n",
    "How many value comparisons have to be made?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "8c3d907c1a1dcfb87f4bf40bedb875d1",
     "grade": true,
     "grade_id": "cell-d0d9f6387127340b",
     "locked": false,
     "points": 0,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "YOUR ANSWER HERE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "e24f3b417fc241200a5743edb69fc5c2",
     "grade": false,
     "grade_id": "cell-9b602b091fb02f67",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "\n",
    "\n",
    "## 4) Value Iteration in Stochastic Environments\n",
    "\n",
    "All of the pubs have different special offers on some days of the week.\n",
    "Due to general confusion you have no clue, which day of the week we currently have.\n",
    "You only know, for example, that Globetrotter has one happy-hour-day per week, but Black Sheep has four days per week.\n",
    "So, the chance to get a positive reward in the Black Sheep is higher than in the Globetrotter. \n",
    "\n",
    "To find the best path we can use the Bellman optimality equation we know from the lecture:\n",
    "\n",
    "$v_\\pi(x_k) = \\text{max}_{u_k\\in \\mathcal{U}} \\mathbb{E}\\left[R_{k+1} + \\gamma v_\\pi(X_{k+1}|X_k = x_k, U_k = u_k)\\right]$ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "140f9155c1b7cdfbfc5d5ef3b364dd8a",
     "grade": false,
     "grade_id": "cell-6851b19753ed7028",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## Comparison to lecture:\n",
    "In the tree example from lecture we have deterministic rewards and a stochastic state transition.\n",
    "So $v_\\pi(x_k) = \\text{max}_{u_k\\in \\mathcal{U}} r_x^u + \\gamma \\Sigma_{x_{k+1}\\in \\mathcal{X}}p_{xx'}^u v_\\pi(x_{k+1})$\n",
    "\n",
    "![](TreeExampleVL.PNG)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "9d40e8313e619c319fa6ce5061ef6a68",
     "grade": false,
     "grade_id": "cell-b78d669dd6df6f46",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "In our problem we have deterministic state transitions because we reach the bar we plan to visit for sure.\n",
    "But the reward in our case has a stochastic offset.\n",
    "If happy-hour-day (randomly, we do not know the weekday), we get an additional positive reward.\n",
    "The probability to get that is dependent on the number of happy-hour-days per week.\n",
    "For example:\n",
    "\n",
    "![](Stochastic_Rewards.png)\n",
    "\n",
    "As can be seen, in Globetrotter we have in 1 of 7 cases (days) an additional happy-hour-reward and in Black Sheep in 4 of 7 cases.\n",
    "\n",
    "The states are defined in the following order:\n",
    "\n",
    "$\\mathcal{X} = \\left\\lbrace \\begin{matrix}\n",
    "\\text{Start: Home}\\\\\n",
    "\\text{Auld Triangle}\\\\\n",
    "\\text{Lötlampe}\\\\\n",
    "\\text{Globetrotter}\\\\\n",
    "\\text{Black Sheep}\\\\\n",
    "\\text{Limericks}\\\\\n",
    "\\text{Fat Louis}\\\\\n",
    "\\text{End: Home}\\\\\n",
    "\\end{matrix}\n",
    "\\right\\rbrace$\n",
    "\n",
    "The probability to get the positive reward (happy hour) is defined by:\n",
    "\n",
    "$p_{xr_+} = \\left[ \\begin{matrix}\n",
    "\\frac{3}{7} & \\frac{1}{7} & \\frac{1}{7} & \\frac{1}{7} & \\frac{1}{7} & 0 & 0\\\\\n",
    "\\frac{6}{7} & \\frac{4}{7} & \\frac{4}{7} & \\frac{5}{7} & \\frac{5}{7} & 0 & 0\\\\\n",
    "\\end{matrix}\n",
    "\\right]$\n",
    "\n",
    "                    \n",
    "$r_{+} = \\left[ \\begin{matrix}\n",
    "12 & 16 & 16 & 16 & 16 & 0 & 0\\\\\n",
    "6 & 10 & 10 & 8 & 8 & 0 & 0\\\\\n",
    "\\end{matrix}\n",
    "\\right]$  \n",
    "\n",
    "The probability to get the no extra reward is $p_{xr_-} = 1 - p_{xr_+}$.\n",
    "In that case you take the \"no extra reward\" $r_-$ is zero in all cases.\n",
    "\n",
    "$r_{-} = \\left[ \\begin{matrix}\n",
    "0 & 0 & 0 & 0 & 0 & 0 & 0\\\\\n",
    "0 & 0 & 0 & 0 & 0 & 0 & 0\\\\\n",
    "\\end{matrix}\n",
    "\\right]$  \n",
    "\n",
    "\n",
    "The actions to choose are $\\textit{up}$ and $\\textit{down}$ (for states Li and F, $\\textit{up}$ and $\\textit{down}$ mean the same).\n",
    "\n",
    "So if you are at home and you go $\\textit{up}$ you get a fixed reward of $-3$ on the way.\n",
    "With a probability of $p_{x=0,r_+} = \\frac{3}{7}$ there is happy hour in the Auld Triangle and you get an additional reward of $+12$. \n",
    "\n",
    "\n",
    "\n",
    "1. Examine the pseudocode for value iteration as presented in the lecture. Does this pseudocode already contain the concept of a stochastic reward and where do we find it?\n",
    "2. Make use of value iteration to (use $\\gamma = 1$):\n",
    "    1. Find the state value for each state\n",
    "    2. Find the optimal policy\n",
    "3. Check your solution by dynamic programming by hand like in 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "3a2111179e45e31aba86743f39e3926e",
     "grade": false,
     "grade_id": "cell-baaebf226260bc67",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "### Pseudocode:\n",
    "***\n",
    "- **input:** Full model of the MDP i.e. $\\left\\langle\\mathcal{X}, \\mathcal{U}, \\mathcal{P}, \\mathcal{R}, \\gamma \\right\\rangle$\n",
    "- **parameter:** $\\delta>0$ as accuracy termination threshold\n",
    "- **init:** $v_0(x_k)\\, \\forall \\, x_k\\in\\mathcal{X}$ arbitrary except $v_0(x_k)=0$ if $x_k$ is terminal\n",
    "- **repeat** \n",
    "    - $\\Delta \\leftarrow 0 $\n",
    "    - **for** $\\forall \\, x_k\\in\\mathcal{X}$\n",
    "        - $\\tilde{v}\\leftarrow \\hat{v}(x_k)$\n",
    "\t\t- $\\hat{v}(x_k)\\leftarrow  \\max_{u_k\\in\\mathcal{U}}\\left(\\mathcal{R}^u_x + \\gamma\\sum_{x_{k+1}\\in\\mathcal{X}}p_{xx'}^u \\hat{v}(x_{k+1})\\right)$\n",
    "\t\t- $\\Delta \\leftarrow \\max\\left(\\Delta, |\\tilde{v}-\\hat{v}(x_k) |\\right)$\n",
    "    - **end**\n",
    "- **until** $\\Delta < \\delta$\n",
    "- **output:** Deterministic policy $\\pi\\approx\\pi^*$, such that\n",
    "\n",
    "$\\pi(x_k)\\leftarrow  \\text{arg} \\, \\text{max}_{u_k\\in\\mathcal{U}}\\left(\\mathcal{R}^u_x + \\gamma\\sum_{x_{k+1}\\in\\mathcal{X}}p_{xx'}^u \\hat{v}(x_{k+1})\\right)$\n",
    "***\n",
    "Value iteration (note: compared to policy iteration, value iteration doesn't require an initial policy but only a state-value guess)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "e2780e11a9611bf27a44217794fa387d",
     "grade": false,
     "grade_id": "cell-d75a874a365ec4e3",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## 4) Solution \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "bc3eb35d484b1659971ebae96b4c6368",
     "grade": false,
     "grade_id": "cell-2844ac6977528497",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "np.set_printoptions(linewidth=100)\n",
    "\n",
    "r_ways = np.array([[-3, -2, -3, -4, -5, -6, -7],\n",
    "                   [-1, -4, -5, -5, -6, -6, -7]]) # fixed rewards for the upwards or downwards path\n",
    "\n",
    "p_xr = np.array([[3/7, 1/7, 1/7, 1/7, 1/7, 0, 0],\n",
    "                 [6/7, 4/7, 4/7, 5/7, 5/7, 0, 0]]) #probability of success for the upwards or downwards path\n",
    "\n",
    "r_happy = np.array([[12, 16, 16, 16, 16, 0, 0],\n",
    "                    [ 6, 10, 10,  8,  8, 0, 0]])\n",
    "\n",
    "expected_rewards = r_ways + p_xr*r_happy + (1-p_xr)*0\n",
    "values = np.zeros([8])\n",
    "\n",
    "\n",
    "delta = 0.1 # lower tolerance boundary\n",
    "\n",
    "# YOUR CODE HERE\n",
    "raise NotImplementedError()\n",
    "print(values)\n",
    "print(iteration_idx)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "ec12b2636ffd086d993475e24877fb44",
     "grade": false,
     "grade_id": "cell-62c7adb60e0f7d2f",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# YOUR CODE HERE\n",
    "raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "b04cf99f4ad774a6f4bc94901ce7f3a0",
     "grade": true,
     "grade_id": "cell-ed9723bfe6f22735",
     "locked": false,
     "points": 0,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "YOUR ANSWER HERE"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
